3370. MERGSORT - Mergesort

Simple. Sort the numbers on the standard input using the merge sort algorithm. Don't try to cheat by just calling your build in functions... I can see your source.

Input. On the standard input you will receive n (1 ≤ n ≤ 100000). Each number will fit in 32-bit integer.

Output. Output the same integers in a sorted manner. Smallest to largest.

Sample Input	Sample Output
7 3 2 5 4 3	2 3 3 4 5 7

РЕШЕНИЕ

сортировка слиянием

Анализ алгоритма

Реализуем сортировку слиянием.

Реализация алгоритма

Реализуем собственную функцию слияния.

#include <cstdio>

#include <string>

#include <vector>

using namespace std;

void merge(int *a, int bleft, int bright, int cleft, int cright)

{

// a[bleft..bright] and a[cleft..cright]

// are merged into a[bleft..cright]

int i, left = bleft, len = cright - bleft + 1;

int *res = new int[len];

for(i = 0; i < len; i++)

{

if ((bleft > bright) || (cleft > cright)) break;

if (a[bleft] <= a[cleft]) res[i] = a[bleft], bleft++;

else res[i] = a[cleft], cleft++;

}

while (bleft <= bright) res[i++] = a[bleft++];

while (cleft <= cright) res[i++] = a[cleft++];

for(i = left; i < left + len; i++) a[i] = res[i - left];

delete[] res;

}

void mergeSort(int *a, int left, int right)

{

if (left >= right) return;

int middle = (left + right) / 2;

mergeSort(a,left,middle);

mergeSort(a,middle+1,right);

merge(a, left, middle, middle + 1, right);

}

int m[100010], i, j;

int main(void)

{

i = 0;

while(scanf("%d",&m[i]) == 1) i++;

i--; mergeSort(m, 0, i);

for(j = 0; j < i; j++) printf("%d ",m[j]);

printf("%d\n",m[i]);

return 0;

}

Реализация алгоритма при помощи встроенной функции merge

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

void merge(vector<int> &a, int bleft, int bright,

int cleft, int cright)

{

// a[bleft..bright] and a[cleft..cright]

// are merged into a[bleft..cright]

int len = cright - bleft + 1;

vector<int> res(len);

merge(a.begin() + bleft, a.begin() + bright + 1,

a.begin() + cleft, a.begin() + cright + 1, res.begin());

copy(res.begin(),res.end(),a.begin() + bleft);

}

void mergeSort(vector<int> &a, int left, int right)

{

if (left >= right) return;

int middle = (left + right) / 2;

mergeSort(a,left,middle);

mergeSort(a,middle+1,right);

merge(a, left, middle, middle + 1, right);

}

vector<int> m;

int i, val, n;

int main(void)

{

for(n = 0; scanf("%d",&val) == 1; n++)

m.push_back(val);

mergeSort(m, 0, n - 1);

for(i = 0; i < n; i++) printf("%d ",m[i]);

printf("\n");

return 0;

}